When the same object is photographed using two horizontally aligned cameras, a deviation is caused in the horizontal direction at positions of the object in the two photographed images due to a difference between the camera positions. The difference in the position of the object between both images is called a “disparity.” The distance from the camera to the object is proportional to a reciprocal of the disparity. That is, the disparity decreases as the distance increases and the disparity increases as the distance decreases.
Conventionally, block matching is widely used as a technique for calculating a disparity. Block matching calculates a disparity by cropping the respective images photographed by the two cameras into small regions (blocks) and searching for locations where a similarity (correlation value) in the small regions between both images becomes maximum. More specifically, when an image photographed by one camera (e.g., the left image photographed by the camera disposed on the left side) is used as a reference, a range of the image photographed by the other camera (e.g., the right image photographed by the camera disposed on the right side) in which the similarity is found corresponds to blocks in a range from the same coordinates as coordinates of a reference block in the left image to coordinates located by a maximum disparity (e.g., 128 pixels) away to the left side in the horizontal direction.
This block matching is simple processing and can basically calculate disparities at points independently of each other, and thereby enables high speed calculations. However, block matching has a problem that it is difficult to accurately calculate a disparity in a region where there is no texture or a region where there is a repetitive pattern.
On the other hand, a scheme (global matching) is proposed these days in which a cost function for disparities of all pixels in an image is defined and a combination of disparities that minimizes the function is obtained. Since this global matching performs global disparity estimation, it is possible to more accurately calculate a disparity even in a region where there is no texture or a region where there is a repetitive pattern.
However, global matching calculates a correlation value for each pixel using the same technique as block matching and then optimizes the own calculation result using calculation results of adjacent pixels. Global matching then integrates the optimized calculation results for pixels of a whole screen and calculates a disparity. That is, the accuracy is improved in global matching compared to block matching, whereas there is a problem that the amount of calculation or the amount of memory for temporarily storing calculation results becomes enormous.
Furthermore, it is realistically difficult to dispose two cameras completely horizontally and a deviation in the vertical direction or deviation in the rotation direction may be generated. A method may also be considered in which based on the premise that there is a certain degree of deviation in the vertical direction, the search range of similarity is widened not only in the horizontal direction but also in the vertical direction. In this case, there is another problem that the number of functional units and/or the amount of memory necessary to calculate a correlation value further increases.